题解 P1453 【城市环路】

发表于 | 更新于

基环树上$dp$

会了这道题就可以顺便$A$了P2607 [ZJOI2008]骑士

由于只有$n$条边，每个点之间互通，所以图就是一颗基环树

所以只需要$dfs$找环，在环上找任意一条边，枚举这条边的两端中其中一端不选(因为两端不能同时选，所以至少有一端不选)，然后进行树形$dp$即可，由于然后这道题就和没有上司的舞会一样了。

dfs找环：

一边走一边用一个$vis$数组标记，回溯时$vis$清零，如果当前点的儿子上有$vis$标记,那么这个点和它的儿子就在环上。

树形$dp$:

设$f[u][0/1]$表示u这个节点选$(0)$或不选$(1)$的最大价值（这里$v$表示u的所有子节点)

$f[u][1]=\sum f[v][0]$

$f[u][0]=\sum max(f[v][0],f[v][1])$

答案就是$f[root][0]$,这里的$root$就是枚举的一端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define int long long
#define re register
#define inf 0x3f3f3f3f
#define N 393939*7
using namespace std;
struct node{
    int to,next;
}e[N<<1];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int now,la,n,ans,cnt,head[N],f[N][2],vis[N],fa[N],v[N];
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa,int rt,int unrt){
    f[u][0]=0;f[u][1]=v[u];vis[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa||(u==rt&&v==unrt))continue;
        if (v!=rt){
            dfs(v,u,rt,unrt);
            f[u][1]+=f[v][0];
            f[u][0]+=max(f[v][1],f[v][0]);
        }
    }
}
void dfss(int u,int fa){
    vis[u]=1;
    for (int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if (v==fa)continue;
        if (vis[v]){la=v;now=u;return;}
        dfss(v,u);
    }
    vis[u]=0;
}
void lxy(int u){
    now=u,la=0;
    dfss(u,0);
    dfs(now,0,now,la);
    int res=f[now][0];
    dfs(la,0,la,now);
    ans+=max(res,f[la][0]);
    return;
}
signed main(){
    n=read();
    for (int i=1;i<=n;++i)
        v[i]=read();
    for (int i=1;i<=n;++i){
        int u=read()+1,v=read()+1;
        add(u,v);add(v,u);
    }
    double K;
    scanf("%lf",&K);
    for (int i=1;i<=n;++i)
        if (!vis[i])
            lxy(i);
    double res=1.0*K*ans;
    printf("%.1lf",res);
    return 0;
}